googologywikiaorg-20200223-history
User talk:Username5243/BMS vs UNOCF
Proof of some stuff : I'll prove that PrSS (Pr'imitive '''S'equence 'S'ystem), a.k.a 1-row BMS behaves like Username describes it. That is, given two matrices X and Y, each one being possibly empty, and assuming standardness of the following expression, X(n)Y(n+1)m expands to X(n)Y...(n)Y, where "(n)Y" is repeated m times. First, we need to assume that BM2.3 and Nish's ruleset behave the same way in PrSS Theorem 1 : Delta is always equal to (0) Proof: Any PrSS element is of the form (n). The case for n=0 is trivial. Delta is of the form (d1,...,d(x-1),0,..,0), where x is the index of the last nonzero entry of the rightmost element. Thus, Delta = (0) for any rightmost element (n). ' ''Theorem 2 : If the rightmost element is (m), then the bad root is the rightmost occurence of (a) for any a= m+1. Thus, B is the rightmost element that is not discarded, which makes it the second-to-last non-discarded element (the last being the rightmost element). Hence, the bad root is guaranteed to be the rightmost occurence of (m), by definition. ''Theorem 3 : If a matrix M is equal to (a_0)(a_1)...(a_i)...(a_(n-1))(a_n), where i is the smallest i such that a_i < a_n, then Mx expands to (a_0)(a_1)...(a_i)...(a_(n-1))...(a_i)...(a_(n-1)), where "(a_i)...(a_(n-1))" is repeated x times Proof : By Theorem 2, (a_i) is the bad root, and by definition, "(a_i)...(a_(n-1))" is the bad part. Since delta is always (0) by Theorem 1, nothing is added to the elements of the bad part. If we let B be the bad part and G the good part (everything to the left of the bad part), then Mx = G+B+...+B, where + is sequence concatenation, and where B is concatenated x times by definition. (This is probably overly formal. Or for all I know this is actually too informal, fuck anything I say. This is my first time actually writing a proof, so please give me tips to improve) Syst3ms (debate about whether funky kong is god incarnate) 17:51, August 22, 2018 (UTC) : Proof of Theorem 2 seems to have two errors. Sorry if I am incorrect. : First, your argument : > Given some rightmost element (m+1), the sequence reduction algorithm discards any element (a) iff a >= m+1. : has a counterexample \((0)(1)(2)(1)(2)\), under the assumptipon that \(m\) is a typo of \(n\). In this case, you have \(n+1 = m+1 = 2\), but the left \(2\) is not discarded even though \(2 \geq m+1 = n+1 = 2\). : EDITED: I first thought that "the right most element \((m+1)\)" meant the rightmost \((1)\) after removing the rightmost \((2)\), but now I guess that \(m\) is a typo of \(n\). In both cases, your argument seems to be wrong by the same counterexample. : Secondly, your argument : > Thus, the rightmost occurence of (m) is the rightmost element that is not discarded : lacks the proof of the occurence of \((m)\) at the position left to the rightmost \((m+1)\). I mean that you need to prove that there is no sequence like \((0)(1)(3)(4)\), where \(m+1 = 3\) and hence \(m = 2\), in the expansion of standard primitive sequences. : p-adic 21:40, August 22, 2018 (UTC) : : >> I think I fixed proof of theorem 2 : : >> That's something tough to prove, because describing how standard PrSS expressions expand is precisely what we're trying to do here. My guess is that we would need to use a proof by contradiction. I don't think I'll be up for the challenge though. : Syst3ms (debate about whether funky kong is god incarnate) 09:20, August 23, 2018 (UTC) : : Okay, I edited the proof of theorem 2. It now also works with nonstandard expressions such as (0)(2). : : Syst3ms (debate about whether funky kong is god incarnate) 16:21, August 23, 2018 (UTC) :: Now the remaining arugument is the case where there is no bad root. Say, \((0)(1)(2)(0)\) in the standard case, and \((3)(2)(4)(2)\) in the non-standard case (if you care about non-standard expressions). :: p-adic 21:59, August 23, 2018 (UTC) ::: Ok, I'll prove that there is always a bad root. First off, remember that the case when a matrix ends with a (0) is trivial, since it just gets cut off. Then, we define standard form as such: ::: - (0,...,0)(1,...,1) is standard for any amount of 0s and 1s. The case for the empty matrix is trivial. ::: - A matrix is standard iff it can be obtained by expanding and truncating another standard matrix. ::: A (0) can be discarded by sequence reduction iff there is another (0) to the right in the matrix that may be a bad root (i.e that isn't the rightmost element, to which case it is trivial). Since a matrix is standard iff it can be obtained by repeated expansions and truncations of a matrix of the form (0,...,0)(1,...,1). The (0,...,0) element thus cannot be discarded (unless the matrix only consists of (0,...,0)s, which is a trivial case), which guarantees a bad root in every standard matrix. ::: ::: Sorry if this is phrased poorly, I really don't know how to structure this. ::: Syst3ms (debate about whether funky kong is god incarnate) 15:57, August 24, 2018 (UTC) :::